1. Technical Field
The invention is an improvement to a class of shift error correcting modulation codes which are uniquely adapted to correct shift errors in run length limited (RLL) channel encoded data. The improvement achieved in the present invention enables a decoder employing such a code to correct not only shift errors but also additive errors and errors due to synchronization slips as well.
2. Background Art
(A.) Shift Correcting Modulation Codes
Shift error correcting modulation codes were first disclosed in U.S. patent application Ser. No. 07/200,166 filed May 31, 1988 entitled "Shift Correction Code for Channel Encoded Data" by Dennis George Howe et al. and assigned to the assignee of the present application. As understood in that application as well as the present application, the term "shift error" in RLL encoded data refers to an error generated by the shifting of the position of any one of the 1's ("start bits") in a binary RLL sequence such as EQU 10001000000100010000001.
If for example the second 1 in the foregoing sequence were shifted by one bit position to the "right", the sequence would change to EQU 10000100000100010000001.
In the foregoing example, the sequence containing the shift error is obtained by adding (modulo 2) the binary error pattern EQU 00001100000000000000000
to the original RLL binary sequence. We note that this error pattern has weight two, i.e., it contains exactly two non-zero bits.
The foregoing original and shift error corrupted binary RLL sequences may also be expressed as sequences of "runs" (a binary RLL sequence run consists of a 1 ("start bit") and all the contiguous zeros ("run bits") that immediately follow it and is denoted by an integer value ranging from d+1 to k+1 in a d,k-constrained RLL code). Expressing the above binary RLL sequences as sequence of runs we obtain for the original sequence EQU 4, 7, 4, 7
and for the shift error corrupted sequence EQU 5, 6, 4, 7.
Thus, in the foregoing example, the single shift error changed the run length (or run value) of two RLL runs (or "RLL symbols"), namely the first run whose length was increased, and the second run whose length was decreased by this error. Thus, the effect of a single shift error is essentially double that of other types of simple errors in that it corrupts two symbols (i.e., two bits or two runs) and therefore requires twice the redundant encoding overhead of prior art error correction codes for successful decoding, a significant problem.
As described in the referenced patent application, shift error correcting modulation codes solve this problem by transforming run sequences to cumulative sum sequences prior to shift correction encoding. This transformation reduces the effect of a shift error, i.e., it ensures that a shift error corrupts only one code symbol instead of two. To see this, consider the original and shift error corrupted run sequences of the above example: the original run sequence was EQU {x.sub.0, x.sub.1, x.sub.2, x.sub.3 }={4, 7, 4, 7}
and its corresponding cumulative sum sequence is EQU {s.sub.0, s.sub.1, s.sub.2, s.sub.3 }={4, 11, 15, 22}.
(Note: the sum elements are calculated using ##EQU1## The shift error corrupted run sequence was EQU {x.sub.0, x.sub.1, x.sub.2, x.sub.3 }={5, 6, 4, 7}
and its corresponding sum sequence is EQU {s.sub.0, s.sub.1, s.sub.2, s.sub.3 }={5, 11, 15, 22}.
Clearly, only one element of the sum sequence, not two, was affected by the shift error. This is relevant to shift error correction coding because the symbols on which shift error correction codes are formed are mod p reductions of the cumulative sum sequence elements (where p is an odd prime).
We now give a brief review of shift error correction coding. The RLL channel encoded data is divided into message blocks. A check block of RLL data is generated for each message block in accordance with the shift error correction modulation code; this check block is appended to the message block. When the shift correction encoded RLL data is played back or received, a shift correction decoder uses the check block information to locate and correct shift errors in the entire code block, which is comprised of both the message and check blocks. The shift correction code employed requires less redundant encoding overhead than prior art error correction codes to correct a single shift error.
In essence, the check block of RLL data is computed in accordance with the shift correction code by transforming the value of each message RLL run symbol, called an x-space symbol, in accordance with a transformation in which each RLL run symbol value is summed with the preceding run symbol values in the message block. The resulting transformed symbols, called s-space (sum space) symbols, are then reduced modulo p to generate s'-space symbols, where p is an odd prime number defining a Galois field GF(p). If only single shift errors may occur, it suffices if p=3, which is the number of shift error possibilities for each RLL run symbol, namely, (0) no shift and therefore no error, (1) forward or "right-ward" shift and (-1), or equivalently (2), backward or "left-ward" shift. The message block of s'-space symbols thus produced are then encoded in accordance with a code (called the "base" code) over GF(p) using well-known encoding techniques to generate a check block of redundant s'-space check symbols. Together, the message block and check block of s'-space symbols comprise a logical codeword of the GF(p) base code. The s'-space check symbols are then transformed back to x-space check symbols essentially by using the inverse of the x-space-to-s-space transformation mentioned above. The x-space check symbols are then transformed to RLL binary data and appended to the corresponding message block of RLL data to form a complete block of RLL data which is a physical representation of the logical codeword. The RLL data has thus been shift correction encoded.
Upon receiving the complete block of the shift correction encoded RLL data, the shift correction decoder uses the foregoing encoding process--or one very similar to it--to transform each of the received x-space message and check symbols to corresponding s'-space symbols. The syndrome of the resulting block of s'-space symbols with respect to the GF(p) base code is then computed (using any method for obtaining such a syndrome) and used to locate and correct (again, using conventional techniques) any erroneous s'-space symbols in the block. The corrected logical codeword (s'-space) is finally transformed to x-space, thus correcting shift errors occurring in the received RLL message block data. The number of single-place shift errors which may occur in a received RLL data block without surpassing the capability of the code is given by the largest integer contained in (d.sub.min -1)/2, where d.sub.min is the minimum distance of the chosen base code. The permissible number of RLL bit positions which a correctable shift error may encompass may be increased by increasing p in GF(p).